[CF1238E]Keyboard Purchase

2019-12-19
#idea #动态规划Dp #状态压缩

题意

给定包含m种字符的字符串，找到一种键盘，使它是m个字符的一种排列

打完这段字符串，会在键盘上移动一些距离，求距离最小值

题解

这道题不能用传统方式去看，因为前面字符的排列方式会影响后面的Dp，不得不退化到n!

最好的情况是令这m个字符在键盘上距离皆为1，令$f_S$为当前已经确定S中的字符

显然若一个字符已经确定，而另一个没有确认且没有在这次被确认，它们之间的距离会+1

得到转移

调试记录

无

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[1 << 20], n, m, c[20][20];
char str[(int)1e5];
int main(){
	scanf("%d%d%s", &n, &m, str);
	for (int i = 0; i < n - 1; i++) c[str[i] - 'a'][str[i + 1] - 'a']++, c[str[i + 1] - 'a'][str[i] - 'a']++;
	memset(f, 0x3f, sizeof f); f[0] = 0;
	for (int i = 0; i < (1 << m); i++){
		int t = 0;
		for (int j = 0; j < m; j++)
			for (int k = j + 1; k < m; k++)
				if ((i >> j & 1) ^ (i >> k & 1)) t += c[j][k];
		for (int j = 0; j < m; j++)
			if (i >> j & 1) f[i] = min(f[i], f[i ^ (1 << j)] + t);
	} printf("%d\n", f[(1 << m) - 1]);
	return 0;
}